// 示例1
let data = [
  // 下一行也可以添加pid: 0，即替换为{id: 1, name: 'r1', pid: 0},
  { id: 1, name: 'r1' },
  { id: 2, name: 'r2', pid: 1 },
  { id: 3, name: 'r3', pid: 2 },
  { id: 4, name: 'r4', pid: 3 },
  { id: 5, name: 'r5', pid: 2 }
]
// 转换结果
let res = null

/**
 * 数组转树 非递归求解
 * 利用数组和对象相互引用  时间复杂度O(n)
 *
 * @param {array} arr 扁平化数组
 * @return {array} 树结构
 */
/* function toTree(arr) {
  let result = []
  if (!Array.isArray(arr)) {
    return result
  }
  arr.forEach(item => {
    delete item.children
  })
  let map = {}
  arr.forEach(item => {
    map[item.id] = item
  })
  arr.forEach(item => {
    let parent = map[item.pid]
    // 如果想保留pid属性，则注释掉下一行
    delete item.pid
    if (parent) {
      ;(parent.children || (parent.children = [])).push(item)
    } else {
      result.push(item)
    }
  })

  return result
}

res = toTree(data) */

/**
 * 数组转树 递归求解
 *
 * @param {array} arr 扁平化数组
 * @return {array} 树结构
 */
/* function toTree(data, pid) {
  let result = []
  let  temp
  for (var i = 0; i < data.length; i++) {
    if (data[i].pid == pid) {
      let obj = { name: data[i].name, id: data[i].id }
      temp = toTree(data, data[i].id)
      if (temp.length > 0) {
        obj.children = temp
      }
      result.push(obj)
    }
  }

  return result
}

data = [
  { id: 1, name: 'r1', pid: 0 },
  { id: 2, name: 'r2', pid: 1 },
  { id: 3, name: 'r3', pid: 2 },
  { id: 4, name: 'r4', pid: 3 },
  { id: 5, name: 'r5', pid: 2 }
]

res = toTree(data, 0) */


// 示例2
data = [
  {
    id: 1,
    name: 'r1',
    pid: 0,
    children: [
      {
        id: 2,
        name: 'r2',
        pid: 1,
        children: [
          {
            id: 3,
            name: 'r3',
            pid: 2,
            children: [
              {
                id: 4,
                name: 'r4',
                pid: 3
              }
            ]
          },
          {
            id: 5,
            name: 'r5',
            pid: 2
          }
        ]
      }
    ]
  }
]

/**
 * 树转数组扁平化结构
 * 深度优先遍历 堆栈 后进先出
 *
 * @param {array} tree 树结构
 * @return {array} 扁平化数组
 */
/* function toArr(tree) {
  let stack = tree
  let result = []
  while (stack.length != 0) {
    let pop = stack.pop()
    result.push({
      id: pop.id,
      name: pop.name,
      pid: pop.pid
    })
    let children = pop.children
    if (pop.children) {
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push(children[i])
      }
    }
  }

  return result
}

res = toArr(data) */

/**
 * 树转数组扁平化结构
 * 深度优先遍历 递归
 *
 * @param {array} tree 树结构
 * @return {array} 扁平化数组
 */
/* function toArr(tree) {
  let result = []
  tree.forEach( item => {
    let loop = tree => {
      result.push({
        id: tree.id,
        name: tree.name,
        pid: tree.pid
      })
      let children = tree.children
      if(children) {
        for(let i = 0; i < children.length; i++) {
          loop(children[i])
        }
      }
    }
    loop(item)
  })

  return result
}

res = toArr(data) */

/**
 * 树转数组扁平化结构
 * 广度优先 队列 先进先出
 *
 * @param {array} tree
 */
function toArr(tree) {
  let stack = tree
  let result = []
  while(stack.length != 0) {
    let shift =  stack.shift()
    result.push({
      id: shift.id,
      name: shift.name,
      pid: shift.pid
    })
    let children = shift.children
		if(children){
			for(let i = 0; i < children.length; i++){
				stack.push(children[i])
			}
		}
  }

  return result
}

res = toArr(data)

console.log(res)
